//二叉搜索树
public class BinarySearchTree {
    static class TreeNode {
        public int val;

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode left;
        public TreeNode right;

    }
    public TreeNode root;

    //查找元素
    public Boolean search(int val) {
        TreeNode cur = root;
        while(cur!=null) {
            if(cur.val<val) {
                cur = cur.right;
            } else if(cur.val>val) {
                cur = cur.left;
            } else {
                return true;
            }
        }
        //空树直接false
        return false;
    }

    //插入元素
    public void insert(int val) {
        //空树插入直接放根节点
        if (root==null) {
             root = new TreeNode(val);
             return;
        }
        TreeNode cur = root;
        TreeNode parent = null;
        //通过parent找到插入节点的父亲节点
        while(cur!=null) {
            if(cur.val<val) {
                parent = cur;
                cur = cur.right;
            } else if(cur.val>val) {
                parent = cur;
                cur = cur.left;
            } else {
                return;
            }
        }
        //插入
        TreeNode node = new TreeNode(val);
        if (parent.val<val) {
            parent.right = node;
        } else {
            parent.left = node;
        }
    }

    //删除元素
    public void remove(int val) {
        //找要删除元素的位置
        TreeNode cur = root;
        TreeNode parent = null;
        while (cur!=null) {
            if (cur.val<val) {
                parent = cur;
                cur = cur.right;
            } else if(cur.val>val) {
                parent = cur;
                cur = cur.left;
            }else {
                //找到了这个时候就要真正进行删除了
                removeNode(parent,cur);
                return;
            }
        }
    }
    //真正的删除(三种情况)
    private void removeNode(TreeNode parent,TreeNode cur) {
        if (cur.left==null) {
            //1.要删除节点的左边为空
            if (cur==root) {
                //<1>且要删除的节点就是root
                root = cur.right;
            }else if (cur==parent.left) {
                //<2>且要删除的节点是parent的左节点
                parent.left = cur.right;
            }else {
                //<2>且要删除的节点是parent的左节点
                parent.right = cur.right;
            }
        } else if (cur.right==null) {
            //2.要删除节点的右边为空
            if (cur==root) {
                //<1>且要删除的节点就是root
                root = cur.left;
            }else if (cur==parent.left) {
                //<2>且要删除的节点是parent的左节点
                parent.left = cur.left;
            }else {
                //<2>且要删除的节点是parent的左节点
                parent.right = cur.left;
            }
        } else {
            //3.左右都不为空
            TreeNode t = cur.right;
            TreeNode tp = null;//t的parent节点
            //找右数的最小值(也可以找左数的最大值)
            while(t.left!=null) {
                tp = t;
                t = t.left;
            }
            //将右树的最小值覆盖cur
            cur.val = t.val;
            //删除右数的最小值
            //<1>最小值是叶子节点
            if (tp.left==t) {
                tp.left = t.right;
            //<2>最小值不是叶子节点
            } else {
                tp.right = t.right;
            }

        }
    }
}
